# 作者: 陈其志 
# 2025年02月23日21时06分26秒 
# 2716847110@qq.com
import random


class Sort:
    """
    快速排序的核心思想是分治
    """

    def __init__(self, n, nums_range):
        self.n = n  # 排序数目
        self.arr = []
        self.nums_range = nums_range
        self.random_nums()

    def random_nums(self):
        for i in range(self.n):
            self.arr.append(random.randint(0, self.nums_range - 1))

    def partition(self, left, right):
        arr = self.arr
        k = left
        for i in range(left, right):
            # 如果小于分割值，就交换
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_wort(self, left, right):
        """
        分治思想、找partition、递归
        :return:
        """
        if left < right:
            pivot = self.partition(left, right)
            self.quick_wort(left, pivot - 1)  # 递归快排，左边一半，右边一半
            self.quick_wort(pivot + 1, right)


if __name__ == '__main__':
    s = Sort(10, 100)
    print(s.arr)
    s.quick_wort(0, s.n - 1)
    print(s.arr)
